Multipoint communication, especially multipoint communication over the Internet, is for the most part implemented by multicast methods, whereby the same content is delivered to all participating nodes in the session at the same time.
IP multicast has a problem with its complexity with respect to the intermediate node configuration, end node configuration and requirement for Internet service provider participation, for enabling IP layer multicasting. By contrast, application layer multicasting (“ALM”) implements an application layer routing mechanism on top of existing unicast network architectures. ALM is popular and widely used because of its simplicity.
ALM does not require multicast forwarding functions in the IP layer and therefore allows flexible audio video (“AV”) packets forwarding by the members themselves between the participating nodes and AV packet transferring in the application layer.
ALM allows all participants in a specific session to exchange AV contents and streams between the participants without setting up the environment in advance. ALM is therefore suitable for use with AV-based applications such as TV conference between multiple parties.
However, the number of AV streams to be exchanged between participating nodes increase in order of N×(N−1) for N members. It is generally difficult to maintain fair communication costs in a communication network in terms of bandwidth and latency, especially in the Internet environment between end nodes. The Internet as an open network does not guarantee bandwidth-fairness between ALM nodes during the exchange of AV streams by the participating nodes.
Since multiple internet service providers (“ISPs”) maintain routes on the Internet, which is dynamic in nature, minimal stream delivery delay tree building and maintenance for multiple trees is difficult. Routers use unicast route control methods to establish communication channels by detecting the channels connection status which is vary dynamically. Optimal route information is calculated based on available channels for communication use in the Internet. Next, this optimal route information will be exchanged between the routers for audio video communication. In contrary, multicast route control method builds source base trees, in which the transmission source is placed at the root node, using unicast routes as the basic information. Multicast route control method builds route without using information which is required to allow participants of multipoint-to-multipoint communication to use equal bandwidth or information for minimizing the delay. Thus, usage of existing route control technologies as-it-is for route calculation between terminals targeting multipoint-to-multipoint audio video communication will not provide equal share bandwidth link and minimal delay link routes between participant nodes.
Packet routing is carried out in application layer for ALM, so that the participating nodes are organized into groups. Furthermore, in packet routing, the packet forwarding mechanism needs to be made known to all participating nodes.
Network layer routing mechanisms provides short-sited, nearest path construction methods, and therefore does not provide bandwidth-fair distribution tree solution. For the network layer routing mechanism, SBT and minimum spanning tree (“MST”), which are based on the “greedy” concepts of Dijkstra, Bellman-Ford and Prim algorithms for short path formation, are well known. The unicast packet routing over the Internet is based on these algorithms and does not reflect the need for ALM routing.
Thus, these solutions do not take into account the end node network bandwidth and overall network topology, and therefore cause traffic congestion. Furthermore, these solutions cause high network latency and degradation of AV quality for ALM applications.
Hereinafter, the prior art, that is, prim-MST algorithm mechanism will be described using a simple example (FIG. 1). FIG. 1 shows four different locations, that is, Vietnam (VN), Japan (JP), Malaysia (MY) and Singapore (SG), where the capacity of bandwidth B(X) of the channel for each node and the delay D(A, B) between two nodes vary. In this example, transmission rate sets/slots for 8 Mbps, 4 Mbps, 3 Mbps or 2 Mbps are used.
In this case, if the conventional, Prim-MST algorithm based on a “greedy” algorithm mechanism is executed, each of one-to-N distribution trees for N nodes (N=4 in this example) can be calculated as follows.
(1) First, a path for transmitting packets to other nodes is selected for MY, where the available bandwidth is the largest. To be more specific, first, it is necessary to consider whether or not MY is able to secure an 8 Mbps bandwidth for all the other nodes. In this case, if a path is selected through which MY can transmit packets to VN and SG directly, an 8 Mbps bandwidth can be secured. However, the delay D=300 ms between MY and JP exceeds the maximum latency 250 ms, and therefore it is not possible to select a path through which MY can transmit packets directly to JP. Then, for the packet transmission from MY to JP, a path is selected through which packets are transmitted via SG. By this means, MY is able to secure an 8 Mbps bandwidth for JP (FIG. 2A). As a result, the remaining bandwidth is 20 Mbps for MY, 12 Mbps for SG, 16 Mbps for JP and 6 Mbps for VN.
(2) Next, for SG, where the original available bandwidth is the second largest, a route for transmitting packets to other nodes, is selected. To be more specific, first, it is necessary to consider whether or not SG is able to secure an 8 Mbps bandwidth for all the other nodes. However, if SG secures an 8 Mbps for MY and for VN (8 Mbps×2), the remaining bandwidth for SG exceeds 12 Mbps. SG therefore cannot secure an 8 Mbps bandwidth. Then, next, it is necessary to consider whether SG is able to secure a 4 Mbps bandwidth for all the other nodes. In this case, if a path is selected through which SG is able to transmit packets directly to MY and VN, it is possible to secure a 4 Mbps bandwidth. Furthermore, if a path is selected through which packets are transmitted from SG to JP via VN, SG is able to secure a 4 Mbps bandwidth for JP (FIG. 2B). In this case, the remaining bandwidth is 20 Mbps for MY, 4 Mbps for SG, 16 Mbps for JP and 2 Mbps for VN.
(3) Next, for JP, where the original available bandwidth is the third largest, a route for transmitting packets to other nodes, is selected. To be more specific, first, it is necessary to consider whether JP is able to secure a 4 Mbps bandwidth for all the other nodes. In this case, if a path is selected through which JP is able to transmit packets directly to SG and VN, it is possible to secure a 4 Mbps bandwidth. Furthermore, if a path is selected through which packets are transmitted from JP to MY via SG, JP is able to secure a 4 Mbps bandwidth for MY (FIG. 2C). In this case, the remaining bandwidth is 20 Mbps for MY, 0 Mbps for SG, 8 Mbps for JP and 2 Mbps for VN.
(4) Finally, for VN, where the original available bandwidth is the smallest, a route for transmitting packets to other nodes, is selected. Now, the remaining bandwidth for VN is 2 Mbps, so that a path is selected through which VN is able to transmit packets directly to MY and a 2 Mbps bandwidth is secured. Furthermore, if a path is selected through which packets can be transmitted from VN to JP via MY, VN is able to secure a 2 Mbps bandwidth for JP. Furthermore, if a path is selected through which packets are transmitted from VN to SG via MY and JP, VN is able to secure a 2 Mbps bandwidth for SG (FIG. 2D).
Thus, with the conventional (Prim-MST) N-tree algorithm by constructing N of one-to-N source-based trees, it is possible to establish a TV conference enable the ALM system to establish N-to-N TV conference sessions between participating nodes. This method satisfies the latency requirement based on SBT.    Non-Patent Document 1: Min Sik Kim et. al, “Optimal Distribution Tree for Internet Streaming Media”, Proceedings of the 23rd IEEE ICDCS, May 2003    Patent Document 1: U.S. Patent Application Publication No. 2006/0251062    Patent Document 2: U.S. Patent Application Publication No. 2006/0153100    Patent Document 3: U.S. Patent Application Publication No. 2005/0080894    Patent Document 4: U.S. Patent Application Publication No. 2005/0243722